/*
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 */
package com.l2jfree.tools.util;

//   Copyright (c) 1999 CERN - European Organization for Nuclear Research.

//   Permission to use, copy, modify, distribute and sell this software
//   and its documentation for any purpose is hereby granted without fee,
//   provided that the above copyright notice appear in all copies and
//   that both that copyright notice and this permission notice appear in
//   supporting documentation. CERN makes no representations about the
//   suitability of this software for any purpose. It is provided "as is"
//   without expressed or implied warranty.

import java.util.Arrays;

/*
 * Modified for Trove to use the java.util.Arrays sort/search
 * algorithms instead of those provided with colt.
 */

/**
 * Used to keep hash table capacities prime numbers. Not of interest for users;
 * only for implementors of hashtables.
 * 
 * <p>
 * Choosing prime numbers as hash table capacities is a good idea to keep them
 * working fast, particularly under hash table expansions.
 * 
 * <p>
 * However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to keep
 * capacities prime. This class provides efficient means to choose prime
 * capacities.
 * 
 * <p>
 * Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of 300
 * ints). Memory requirements: 1 KB static memory.
 * 
 * @author wolfgang.hoschek@cern.ch
 * @version 1.0, 09/24/99
 */
public final class PrimeFinder
{
	/**
	 * The largest prime this class can generate; currently equal to
	 * <tt>Integer.MAX_VALUE</tt>.
	 */
	public static final int largestPrime = Integer.MAX_VALUE; // yes, it is
																// prime.
	
	/**
	 * The prime number list consists of 11 chunks.
	 * 
	 * Each chunk contains prime numbers.
	 * 
	 * A chunk starts with a prime P1. The next element is a prime P2. P2 is the
	 * smallest prime for which holds: P2 >= 2*P1.
	 * 
	 * The next element is P3, for which the same holds with respect to P2, and
	 * so on.
	 * 
	 * Chunks are chosen such that for any desired capacity >= 1000 the list
	 * includes a prime number <= desired capacity * 1.11.
	 * 
	 * Therefore, primes can be retrieved which are quite close to any desired
	 * capacity, which in turn avoids wasting memory.
	 * 
	 * For example, the list includes
	 * 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
	 * 
	 * So if you need a prime >= 1040, you will find a prime <= 1040*1.11=1154.
	 * 
	 * Chunks are chosen such that they are optimized for a hashtable
	 * growthfactor of 2.0;
	 * 
	 * If your hashtable has such a growthfactor then, after initially "rounding
	 * to a prime" upon hashtable construction, it will later expand to prime
	 * capacities such that there exist no better primes.
	 * 
	 * In total these are about 32*10=320 numbers -> 1 KB of static memory
	 * needed.
	 * 
	 * If you are stingy, then delete every second or fourth chunk.
	 */
	
	private static final int[] primeCapacities = {
			// chunk #0
			largestPrime,
			
			// chunk #1
			5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 102877, 205759, 411527, 823117,
			1646237,
			3292489,
			6584983,
			13169977,
			26339969,
			52679969,
			105359939,
			210719881,
			421439783,
			842879579,
			1685759167,
			
			// chunk #2
			433, 877, 1759, 3527, 7057, 14143, 28289, 56591, 113189, 226379, 452759, 905551, 1811107, 3622219,
			7244441,
			14488931,
			28977863,
			57955739,
			115911563,
			231823147,
			463646329,
			927292699,
			1854585413,
			
			// chunk #3
			953, 1907, 3821, 7643, 15287, 30577, 61169, 122347, 244703, 489407, 978821, 1957651, 3915341, 7830701,
			15661423,
			31322867,
			62645741,
			125291483,
			250582987,
			501165979,
			1002331963,
			2004663929,
			
			// chunk #4
			1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853, 267713, 535481, 1070981, 2141977, 4283963, 8567929,
			17135863,
			34271747,
			68543509,
			137087021,
			274174111,
			548348231,
			1096696463,
			
			// chunk #5
			31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741, 143483, 286973, 573953, 1147921,
			2295859, 4591721, 9183457, 18366923, 36733847,
			73467739,
			146935499,
			293871013,
			587742049,
			1175484103,
			
			// chunk #6
			599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027, 310081, 620171, 1240361, 2480729, 4961459,
			9922933, 19845871, 39691759, 79383533,
			158767069,
			317534141,
			635068283,
			1270136683,
			
			// chunk #7
			311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037, 164089, 328213, 656429, 1312867, 2625761, 5251529,
			10503061, 21006137, 42012281, 84024581, 168049163,
			336098327,
			672196673,
			1344393353,
			
			// chunk #8
			3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899, 701819,
			1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557, 359339171,
			718678369,
			1437356741,
			
			// chunk #9
			43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159, 46327, 92657, 185323, 370661, 741337, 1482707,
			2965421, 5930887, 11861791, 23723597, 47447201, 94894427, 189788857, 379577741, 759155483, 1518310967,
			
			// chunk #10
			379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649, 195311, 390647, 781301, 1562611, 3125257, 6250537,
			12501169, 25002389, 50004791, 100009607, 200019221, 400038451, 800076929, 1600153859 };
	
	static
	{ // initializer
		// The above prime numbers are formatted for human readability.
		// To find numbers fast, we sort them once and for all.
		
		Arrays.sort(primeCapacities);
	}
	
	/**
	 * Returns a prime number which is <code>&gt;= desiredCapacity</code> and
	 * very close to <code>desiredCapacity</code> (within 11% if
	 * <code>desiredCapacity &gt;= 1000</code>).
	 * 
	 * @param desiredCapacity
	 *            the capacity desired by the user.
	 * @return the capacity which should be used for a hashtable.
	 */
	public static final int nextPrime(int desiredCapacity)
	{
		int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
		if (i < 0)
		{
			// desired capacity not found, choose next prime greater
			// than desired capacity
			i = -i - 1; // remember the semantics of binarySearch...
		}
		return primeCapacities[i];
	}
}
